package com.emeraldparser.util;

import java.util.Deque;
import java.util.Set;

import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;

public abstract class AbstractDeterministicAutomatonBuilder<V, E> {

	protected abstract Iterable<? extends V> getStartVertices();

	protected abstract Iterable<? extends V> getPeers(V vertex);

	protected abstract Iterable<? extends E> getOutboundEdgeLabels(Iterable<? extends V> closure);

	protected abstract Iterable<? extends V> getSuccessors(V vertex, E edgeLabel);

	protected boolean isRejectClosure(ImmutableSet<V> closure) {
		return false;
	}

	protected boolean isAcceptClosure(ImmutableSet<V> closure) {
		return false;
	}

	public Automaton<ImmutableSet<V>, E> buildDeterministicAutomaton() {
		Automaton<ImmutableSet<V>, E> deterministicAutomaton = Automatons.create();
		
		ImmutableSet<V> startClosure = buildClosure(getStartVertices());
		
		Deque<ImmutableSet<V>> unprocessedClosures = Lists.newLinkedList();
		unprocessedClosures.addFirst(startClosure);
		deterministicAutomaton.addVertex(startClosure);
		deterministicAutomaton.addStartVertex(startClosure);
		
		while (!unprocessedClosures.isEmpty()) {
			ImmutableSet<V> closure = unprocessedClosures.removeFirst();
			
			if (isRejectClosure(closure)) {
				deterministicAutomaton.addRejectVertex(closure);
			}
			
			if (isAcceptClosure(closure)) {
				deterministicAutomaton.addAcceptVertex(closure);
			}
			
			for (E edgeLabel : getOutboundEdgeLabels(closure)) {
				ImmutableSet<V> nextClosure = getNextClosure(closure, edgeLabel);
				
				if (deterministicAutomaton.addVertex(nextClosure)) {
					deterministicAutomaton.addDirectedEdge(closure, nextClosure, edgeLabel);
					unprocessedClosures.addLast(nextClosure);
				}
			}
		}
		
		return deterministicAutomaton;
	}

	protected ImmutableSet<V> buildClosure(Iterable<? extends V> initialVertices) {
		Set<V> closureVertices = Sets.newHashSet(initialVertices);
		
		boolean modified;
		do {
			modified = false;
			
			for (V vertex : copy(closureVertices)) {
				modified |= Iterables.addAll(closureVertices, getPeers(vertex));
			}
		} while (modified);
		
		return ImmutableSet.copyOf(closureVertices);
	}

	protected ImmutableSet<V> getNextClosure(Iterable<? extends V> closure, E edgeLabel) {
		Set<V> nextStates = Sets.newHashSet();
		
		for (V vertex : closure) {
			Iterables.addAll(nextStates, getSuccessors(vertex, edgeLabel));
		}
		
		return buildClosure(nextStates);
	}

	//protected void getOutboundEdgeLabels(
	protected <T> Iterable<T> copy(Iterable<? extends T> source) {
		return Lists.newArrayList(source);
	}

}
